# 合并两个有序数组
from typing import List


# 合并两个有序数组
def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
    Do not return anything, modify nums1 in-place instead.
    """
    k = m + n - 1
    i, j = m - 1, n - 1
    while i >= 0 or j >= 0:
        if i == -1:
            nums1[k] = nums2[j]
            j -= 1
        elif j == -1:
            nums1[k] = nums1[i]
            i -= 1
        elif nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

    print(nums1)


# nums1 = [2, 0]
# m = 1
# nums2 = [1]
# n = 1
# merge(nums1, 1, nums2, 1)

from collections import OrderedDict


class LRU:

    def __init__(self, cache: OrderedDict, capacity):
        self.capacity = capacity
        self.cache = cache

    def set(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem()

    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]

    def print_cache(self):
        print(self.cache)


cache = OrderedDict()
lru = LRU(cache, 3)
lru.set(1, 2)
lru.set(2, 3)
lru.set(3, 4)
print(lru.get(1))
lru.print_cache()
